The following relates to the biometric identification arts, object identification arts, security clearance and admittance arts, one-to-many matching arts, and related arts.
One-to-many matching refers generally to the problem of determining whether a person or object is a member of a defined set of persons or objects. Such matching problems arise in diverse applications relating to security clearance, toll parking, invitation-only events, and the like. For example, a biometric identification system acquires a biometric signature of a “query” person requesting admission to a secure area (or attempting to log onto a computer with biometric identification security, or so forth). The biometric signature may, for example, be a feature vector representation of one or more face images, or of an electronically acquired fingerprint, an of optical eye scan, an of electronically recorded handwritten signature, or so forth. The biometric signature of the query person is compared with stored biometric signatures of all authorized persons. If a match is found, then the query person is admitted (or logged into the computer, or so forth).
As another example, a parking lot may be reserved for only authorized vehicles. Such a situation arises in a pre-pay parking lot serving customers who pay a monthly parking fee, or in the case of an employee-only parking lot, or so forth. In this case, the object signature may suitably be a feature vector derived from an image of the vehicle license plate, which is acquired by a camera at a toll gate. The feature vector is compared with a database of feature vectors representing license plate images of authorized vehicles, and the vehicle is admitted if its plate image feature vector matches the feature vector of any plate image in the database. In a variant approach, an image of the vehicle as a whole, or a portion of the vehicle, may be the source of the feature vector that is used as the signature.
Yet another example of a one-to-many matching system is a credit card scanner, which scans a credit card for its number (its “signature”) and compares this signature of the query credit card with all credit card numbers in the database—if no match is found then the card is declined.
One difficulty with one-to-many matching systems is scalability. As the number of authorized persons or objects increases, the size of the database storing the signatures of the authorized persons or objects increases, while processing efficiency degrades. If the number of authorized persons or objects is denoted by N, then the authorized signatures database size, and hence the search time for searching that database, scales with N.
Besides scalability, privacy is another concern with one-to-many matching systems. If the signatures are considered to be sensitive data, then the storage of the authorized signatures in the signatures database presents a possible security issue. Signatures such as fingerprints, credit card numbers, and so forth are generally considered to be sensitive data.
One way to address both scalability and privacy concerns is to employ a less informative signature. For example, a feature vector can be made smaller, with fewer features extracted from the image, so that a smaller signature can be stored. Privacy is enhanced by the reduced information contained in this smaller signature, but search time continues to scale with N. Moreover, the amount of information contained in the stored signature cannot be reduced too much by this technique, as removal of too much information makes the signature ineffective for unambiguously identifying the authorized person or object.
Disclosed in the following are improved data mining techniques that provide various benefits as disclosed herein.